/*
 *  data_structure/tree/huffman/huff.c
 *
 *  (C) 2011 Harry Wei
 */

/*
 * The functions for 
 * data_struct/tree/huffman/main.c.
 */

#include <error.h>
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <stdint.h>

#include "huff.h"

int creat_huffman(struct huffman *huff, int *frequency)
{
	int i = 0;
	int get_lchild;
	int get_rchild;
	int leaf_nodes = LC_NODE_NUM;
	
	for (i = 1; i < leaf_nodes + 1; i++) {
		huff[i].weight = frequency[i];
		huff[i].parent = 0;
		huff[i].lchild = 0;
		huff[i].rchild = 0;
	}	
	for (i = leaf_nodes + 1; i < NODE_NUM + 1; i++) {
		huff[i].weight = 0;
		huff[i].parent = 0;
		huff[i].lchild = 0;
		huff[i].rchild = 0;
	}

#if DEBUG == 0
	/* debug */
	for (i = 1; i < NODE_NUM + 1; i++)
		printf("%d %d %d %d\n", huff[i].weight, huff[i].parent,
					huff[i].lchild, huff[i].rchild);
	/* debug over */
#endif

	for (i = leaf_nodes + 1; i < NODE_NUM + 1; i++) {
		if (huff_select(huff, i - 1, 
			&get_lchild, &get_rchild)) {
			perror("Select Error!\n");
			return 1;
		}
#if DEBUG == 0
		/* debug */
		printf("time %d: %d %d\n", i, get_lchild, get_rchild);
		/* debug over */
#endif

		huff[i].weight = huff[get_lchild].weight 
				+ huff[get_rchild].weight;
		huff[get_lchild].parent = i;
		huff[get_rchild].parent = i;
		huff[i].lchild = get_lchild;
		huff[i].rchild = get_rchild;
	}
	return 0;
}

int huff_select(struct huffman *huf, int temp, 
		int *get_lchild, int *get_rchild)
{
	int i = 1;
	struct huffman get_nums[2] = {{0, 0, 0, 0}, 
					{0, 0, 0, 0}};

	for (i = 1; i < temp + 1; i++) {
		if (0 == huf[i].parent) {
			get_nums[0].weight = huf[i].weight;
			break;
		} else {
			continue;
		}
	}
//	printf("record num: %d\n", get_nums[0].weight);
	for (i = 1; i < temp + 1; i++) {
		if (0 == huf[i].parent) {
			if (get_nums[0].weight >= 
				huf[i].weight) {
				get_nums[0].weight = huf[i].weight;
				get_nums[0].lchild = i;
			}
		} else
			continue;
	}
//	printf("min num: %d\n", get_nums[0].lchild);
	huf[get_nums[0].lchild].parent = 1;
	for (i = 1; i < temp + 1; i++) {
		if (0 == huf[i].parent) {
			get_nums[1].weight = huf[i].weight;
			break;
		} else {
			continue;
		}
	}
//	printf("record num: %d\n", get_nums[1].weight);
	for (i = 1; i < temp + 1; i++) {
		if (0 == huf[i].parent) {
			if (get_nums[1].weight >= 
				huf[i].weight) {
				get_nums[1].weight = huf[i].weight;
				get_nums[1].lchild = i;
			} else {
				continue;
			}
		}
	}
//	printf("min num: %d\n", get_nums[1].lchild);
	*get_lchild = get_nums[1].lchild;
	*get_rchild = get_nums[0].lchild;
//	printf("second: %d\n", get_nums[0].lchild);
//	printf("second: %d\n", get_nums[1].lchild);
	return 0;
}
